package main.java.algorithms;


import main.java.data_structure.Graph;

/**
 * @author Wrb
 * @date 2019/6/13 14:53
 */

//求无权图的连通分量
public class Components {
	private Graph G;                    // 图的引用
	private boolean[] visited;  // 记录dfs的过程中节点是否被访问
	private int ccount;         // 记录联通分量个数
	private int[] id;           // 每个节点所对应的联通分量标记

	// 构造函数, 求出无权图的连通分量
	public Components(Graph graph) {
		G = graph;
		visited = new boolean[G.V()];
		ccount = 0;
		id = new int[G.V()];
		for( int i = 0 ; i < G.V() ; i ++ ){
			visited[i] = false;
			id[i] = -1;
		}

		for (int i = 0; i < G.V(); i++) {
			if (!visited[i]) {
				//深度优先遍历
				dfs(i);
				ccount++;
			}
		}
	}

	private void dfs(int v) {
		visited[v] = true;
		id[v] = ccount;

		for( int i: G.adj(v) ){
			if( !visited[i] )
				dfs(i);
		}
	}

	public int count() {
		return ccount;
	}

	// 查询点v和点w是否连通
	boolean isConnected( int v , int w ){
		assert v >= 0 && v < G.V();
		assert w >= 0 && w < G.V();
		return id[v] == id[w];
	}
}
